package quick;
import java.util.Random;

public class Qclass
{
	public static void QuickSort(int arr[], int p, int r)
	{
		int k;
		int j;
		int x;
		k=p;
		j=r;
		x=arr[(k+j)/2];
		do
		{
		while(arr[k]<x) k++;
		while(arr[j]>x) j--;
		if (k<=j)
		{
			int tmp=arr[k];
			arr[k]=arr[j];
			arr[j]=tmp;
			k++;
			j--;
		}
		}
		while(k<=j);
		if(j>p)
		QuickSort(arr,p,j);
		if(k<r)
		QuickSort(arr,k,r);
	}

	public static void main(String[] args)
	{
		int num=5;
			int[] arr = new int[num];
			Random rand = new Random();
			for(int i=0;i<num;i++)
			{
			arr[i]=rand.nextInt(5);
		     System.out.print(arr[i]);
			}

		int p=0;
		int r=num-1;
		System.out.print('\n');
		long start = System.nanoTime();
		QuickSort(arr,p,r);
		long end = System.nanoTime();
		long traceTime = end-start;
		System.out.println(traceTime);
		for(int i=0; i<num; i++)
		{
		System.out.print(arr[i]);
		}
	}

}
	

